{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ejercicio: Simulación de Bingo\n",
    "Vamos a programar un sencillo juego de bingo. Cada cartón lo codificamos como la lista de enteros que contiene. En `cartones` tenemos todos los cartones que se han vendido"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Datos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cartones = [\n",
    "    [3,10,17,18,28,44,48,54,56,61,63,65,71,72,73],\n",
    "    [4,11,13,20,21,29,30,31,50,55,58,71,78,85,90],\n",
    "    [4,12,14,16,19,33,36,42,48,57,76,78,83,85,91],\n",
    "    [6, 7,11,18,19,24,30,36,39,42,51,65,66,80,89],\n",
    "    [2, 3,10,15,17,26,27,33,76,77,78,83,84,92,95],\n",
    "    [5, 9,13,15,20,29,38,39,42,44,52,76,81,84,98],\n",
    "    [6,10,14,18,20,25,28,33,53,68,74,82,90,91,92],\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definición de la función solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def simulBingo(cartones):\n",
    "    ## Como no queremos modificar el input, tenemos que hacer una copia\n",
    "    cartones = [list(c) for c in cartones]\n",
    "    \n",
    "    # Organizamos la partida \n",
    "    nums = list(range(1, 100))\n",
    "    random.shuffle(nums)  # Barajamos nums\n",
    "    for n in nums:\n",
    "        # Detectamos si ya hay ganadores\n",
    "        ganadores = [ind for (ind, carton) in enumerate(cartones) if not carton]\n",
    "        if ganadores:\n",
    "            return ganadores\n",
    "        \n",
    "        # Quitamos el numero n de los cartones\n",
    "        for carton in cartones:\n",
    "            if n in carton:\n",
    "                carton.remove(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a invocarla unas pocas veces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5]\n",
      "[5]\n",
      "[2]\n",
      "[5]\n",
      "[3]\n",
      "[0]\n",
      "[4]\n",
      "[2]\n",
      "[2]\n",
      "[4]\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    print(simulBingo(cartones))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esta solución tiene un problema: la búsqueda de elementos en listas (`in`, `remove`) es ineficiente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementación con conjuntos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En conjuntos la búsqueda es muy eficiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def simulBingo(cartones):\n",
    "    ## Como no queremos modificar el input, tenemos que hacer una copia\n",
    "    cartones = [set(c) for c in cartones]\n",
    "    \n",
    "    # Organizamos la partida \n",
    "    nums = list(range(1, 100))\n",
    "    random.shuffle(nums)  # Barajamos nums\n",
    "    for n in nums:\n",
    "        # Detectamos si ya hay ganadores\n",
    "        ganadores = [ind for (ind, carton) in enumerate(cartones) if not carton]\n",
    "        if ganadores:\n",
    "            return ganadores\n",
    "        \n",
    "        # Quitamos el numero n de los cartones\n",
    "        for carton in cartones:\n",
    "            carton.discard(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo probamos unas pocas veces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for _ in range(10):\n",
    "    print(simulBingo(cartones))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
